package com.cqs.leetcode;

import com.google.common.base.Stopwatch;

import java.util.concurrent.TimeUnit;

public class ClimbingStairs70 {


    private int[] factors;

    public int climbStairs(int n) {

        if (n == 1) return 1;
        if (n == 2) return 2;
        //f(n) = k * f(2) +  p * f(1)
        //求系数
        getFactors(n - 1);
        return (factors[n - 2] << 1) + factors[n - 3];
    }


    private void getFactors(int n) {
        factors = new int[n];
        factors[0] = 1;
        factors[1] = 1;
        for (int i = 2; i < n; i++) {
            factors[i] = factors[i - 1] + factors[i - 2];
        }
    }


    public static void main(String[] args) throws InterruptedException {
        ClimbingStairs70 cs = new ClimbingStairs70();
        Solution solution  =new ClimbingStairs70.Solution();
        Solution2 solution2  =new ClimbingStairs70.Solution2();
        int size = 44;
        Stopwatch stopwatch = Stopwatch.createStarted();
        System.out.println(solution2.climbStairs(size));
//        TimeUnit.SECONDS.sleep(1);
        stopwatch.stop();
        System.out.println(stopwatch.elapsed(TimeUnit.MILLISECONDS));
        stopwatch = Stopwatch.createStarted();
        System.out.println(solution.climbStairs(size));
        stopwatch.stop();
        System.out.println(stopwatch.elapsed(TimeUnit.MILLISECONDS));
        stopwatch = Stopwatch.createStarted();
        System.out.println(cs.climbStairs(size));
        stopwatch.stop();
        System.out.println(stopwatch.elapsed(TimeUnit.MILLISECONDS));

    }

    private static class Solution {
        private int[] results;

        //超时
        public int climbStairs(int n) {
            if (n == 1) return 1;
            if (n == 2) return 2;
            this.results = new int[n];
            results[0] = 1;
            results[1] = 2;
            return climb(n);
        }

        private int climb(int n) {
            if (results[n - 1] != 0) {
                return results[n - 1];
            }
            return climb(n - 1) + climb(n - 2);
        }
    }

    private static class Solution2 {
        //f(n)表示爬到n个阶梯的方案数量
        //f(n) = f(n-2)+f(n-1)
        public int climbStairs(int n) {
            if (n == 1) return 1;
            if (n == 2) return 2;
            return climbStairs(n - 2) + climbStairs(n - 1);
        }
    }

}
